﻿// 双向链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


#include<stdio.h>
#include<stdlib.h>
//双向链表（即每个节点都有两个指针域，一个指向前，一个指向后）
struct Node
{
    int data;   // 数据域
    Node* pre;  // 前向指针域
    Node* next; // 后向指针域
};

struct Link
{
    Node* head;  // 指向头节点的指针
};

// 生成头节点，地址域全部置空
void Init(Link* link)
{
    link->head = (Node*)malloc(sizeof(Node));
    link->head->pre = NULL;
    link->head->next = NULL;
}
//根据val值删除节点
void Remove(Link* link, int val)
{
    /*建立一个指针，让它指向第一个节点
    * 判空并遍寻数据域等于Val的节点
    * 遍寻完成后剩余的数据域存在三种情况
    * 1、没找到Val，p==null，直接返回，
    * 2、找到val，但是是尾指针时，将上一节点的地址域置为空，
    * 3、找到val，在中间节点，将下一节点的前向指针指向上一节点，将上一节点的后向指针指向后一节点。
    */
    Node* p = link->head->next;
    while (p != NULL && p->data != val)
    {
        p = p->next;
    }
    if (p == NULL)
    {
        return;
    }
    if (p->next != NULL)
    {
        p->next->pre = p->pre;
    }
    p->pre->next = p->next;
    free(p);


}
//双向链表的头插法
void InsertHead(Link* link, int val)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;

    node->pre = link->head;

    node->next = link->head->next;
    if (link->head->next != NULL)
    {
        link->head->next->pre = node;
    }
    link->head->next = node;


}
//双向链表的尾插法
void InserTail(Link* link, int val)
{
    /*定义并初始化一个新节点
    * 找到尾节点
    * 更改节点地址域
    */
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    Node* p = link->head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    node->next = NULL;
    node->pre = p;
    p->next = node;
}
//打印双向链表
void ShowLink(Link* link)
{
    Node* p = link->head->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    Link link;
    Init(&link);
    InsertHead(&link, 20);
    InsertHead(&link, 15);
    InsertHead(&link, 16);
    InsertHead(&link, 19);
    InsertHead(&link, 50);
    InsertHead(&link, 30);
    InsertHead(&link, 40);
    InsertHead(&link, 90);
    ShowLink(&link);
    InserTail(&link, 1);
    InserTail(&link, 2);
    InserTail(&link, 3);
    InserTail(&link, 4);
    InserTail(&link, 5);
    ShowLink(&link);
    Remove(&link, 5);
    ShowLink(&link);
    Remove(&link, 1);
    ShowLink(&link);
    Remove(&link, 90);
    ShowLink(&link);
}